package dmsxl.zifuchuan;

import java.util.Arrays;

/**
 * Author: Zhang Dongwei
 * Date: 2023/4/24 22:19
 * 重复的子字符串
 */
public class zfc7_459 {

    public static void main(String[] args) {
        String s = "abab";
        String s1 = "abcabcabcabc";
        System.out.println(repeatedSubstringPattern(s1));
    }

//    暴力枚举解法, 效果还行
    public static boolean repeatedSubstringPattern1(String s) {
        int n = s.length();
        for (int i = 1; i <= n / 2; i ++){
            if (n % i == 0) {
                boolean match = true;
                for (int j = i; j < n; j++){
                    if (s.charAt(j) != s.charAt(j-i)){
                        match = false;
                        break;
                    }
                }
                if (match)
                    return true;
            }
        }
        return false;
    }

//    字符串匹配解法,效果不好
    public static boolean repeatedSubstringPattern2(String s) {
        String s1 = s + s;
        int pos = s1.indexOf(s, 1);
        if (pos == s.length())
            return false;
        else
            return true;
//        方法二可以直接简化为以下代码
//        return (s + s).indexOf(s, 1) != s.length();
    }

//    利用kmp算法，效果好像也一般
    public static boolean repeatedSubstringPattern3(String s) {
        return kmp(s + s, s);
    }

    public static boolean kmp(String query, String pattern) {
        int n = query.length();
        int m = pattern.length();
        int[] fail = new int[m];
        Arrays.fill(fail, -1);
        for (int i = 1; i < m; ++i) {
            int j = fail[i - 1];
            while (j != -1 && pattern.charAt(j + 1) != pattern.charAt(i)) {
                j = fail[j];
            }
            if (pattern.charAt(j + 1) == pattern.charAt(i)) {
                fail[i] = j + 1;
            }
        }
        int match = -1;
        for (int i = 1; i < n - 1; ++i) {
            while (match != -1 && pattern.charAt(match + 1) != query.charAt(i)) {
                match = fail[match];
            }
            if (pattern.charAt(match + 1) == query.charAt(i)) {
                ++match;
                if (match == m - 1) {
                    return true;
                }
            }
        }
        return false;
    }

    //    利用优化后的kmp算法，效果还行
    public static boolean repeatedSubstringPattern(String s) {
        return kmp1(s);
    }

    public static boolean kmp1(String pattern) {
        int n = pattern.length();
        int[] fail = new int[n];
        Arrays.fill(fail, -1);
        for (int i = 1; i < n; ++i) {
            int j = fail[i - 1];
            while (j != -1 && pattern.charAt(j + 1) != pattern.charAt(i)) {
                j = fail[j];
            }
            if (pattern.charAt(j + 1) == pattern.charAt(i)) {
                fail[i] = j + 1;
            }
        }
        return fail[n - 1] != -1 && n % (n - fail[n - 1] - 1) == 0;
    }
}
